#ifndef UKKONEN_H_
#define UKKONEN_H_

#include <string>
#include <vector>

const int ALPH = (26 * 2 + 1); // размер принимаемого алфавита
const char termChar = '$'; // терминальный символ

class SuffixTree {
private:
	struct edge{
		int to, l, r, ssize; // to - куда ведет ребро, символы с l по r не включая r на ребре, ssize - размер поддерева
	};
	struct vertex{ 
		edge e[ALPH];
		int parent; 
		int height;
		vertex();
	};

	std::vector<vertex> stree;

	int ssz;
	int length;

	std::vector<int> suff;
	const std::string t;

	int ord(char c) const;
	char chr(int x);
	void init(int vnum);
	int new_vertex(int parent);
	int split(int, int, int);
	int add_leaf(int, int, int);
	bool try_c(int, int, int, int);
	void jump(int &, int &, int &, int, int);
	int init_ssizes(int);
public:
	std::string getKth(int);
	explicit SuffixTree(std::string t);
	int getLength() const;
};

#endif  // UKKONEN_H_